/*
357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.
*/

/*
计算各个位置上数字不重复的数
s0 = 1
s1 = 10
s2 = 10*9 + (10 - 9) = 10*9 - 9 + s1
s3 = 10*9*8 + (10*9 - 9*8) + (10 - 9) = 10*9*8 - 9*8 + s2
s4 = 10*9*8*7 + (10*9*8 - 9*8*7) + (10*9 - 9*8) + (10 - 9) = 10*9*8*7 - 9*8*7 + s3
...
答案使用数组直接输出结果
*/
class Solution
{
public:
    int countNumbersWithUniqueDigits(int n)
    {
        if(n < 0) return countNumbersWithUniqueDigits(-n);
        if(n > 10) n = 10;
        const int asn[] = {
            1,
            10,
            91,
            739,
            5275,
            32491,
            168571,
            712891,
            2345851,
            5611771,
            8877691};
        return asn[n];
    }
};
